1. Field of the Invention
The invention relates to signal processing, and more particularly to Fast Fourier Transformation (FFT) of signals.
2. Description of the Related Art
When a Global Positioning System (GPS) receiver receives a GPS signal, the GPS signal is first amplified and filtered. The GPS receiver then attempts to estimate a Doppler frequency shift of the GPS signal with a carrier tracking loop, and lock a code phase of the GPS signal with a code tracking loop. If the satellite sending the GPS signal is moving, the motion of the satellite causes a Doppler frequency shift, which must be adequately compensated before data is extracted from the GPS signal. Additionally, because the satellite combines data carried by the GPS signal with a pseudo random noise (PRN) code before signal transmission, the GPS receiver must track the code phase of the PRN code of the satellite to extract data from the GPS signal.
In one method for estimating the residual Doppler frequency of a received signal, after a carrier signal is removed from a GPS signal, the GPS signal is first delivered to a correlation module which removes the PRN code from the GPS signal. An FFT module then performs a Fast Fourier Transformation (FFT) on the GPS signal to obtain a series of FFT values, according to which the residual Doppler frequency is estimated. Because the estimation is based on FFT values derived from a GPS signal subsequent to correlation processing, the estimation method is referred to as “post-correlation FFT” estimation.
FIG. 1 is a block diagram of a GPS receiver 100. A radio-frequency GPS signal is received by an antenna 102 of the GPS receiver 100. The GPS signal is then amplified by the pre-amplifier 104. A down converter 106 then implements a down conversion on the GPS signal, and an analog to digital converter then converts the GPS signal from analog to digital. The digital GPS signals Sch1˜SchN, each of which corresponds to a satellite channel transmitting signal, are then respectively delivered to corresponding channel processing modules 111˜11N to implement the carrier tracking loop and code tracking loop, and signals Sch1′˜SchN′, without carrier and PRN code, are obtained. The signals Sch1′˜SchN′ are then delivered to a signal processor 120 for extraction of data therefrom.
FIG. 2 is a block diagram of a code removal module 200 of a channel processing module. The channel processing module processes a GPS signal S of a specific satellite channel, and the code removal module 200 removes the PRN code from the GPS signal S. A sine table 202 and a cosine table 204 respectively generate sine values and cosine values according to a carrier number-controlled oscillator 242. The signal S is then multiplied by the sine values and the cosine values to respectively obtain an in-phase signal I and a quadrature signal Q.
The in-phase signal I and the quadrature signal Q are then delivered to a correlation module 210 of the code removal module 200. A PRN code generator 238 first generates three PRN code signals with the same phase difference therebetween, including an early code E, a prompt code P, and a Late code L. A plurality of multipliers 212˜216 and 222˜226 of the correlation module 210 then respectively multiply the in-phase signal I and the quadrature signal Q by the early code E, the prompt code P, and the Late code L to obtain a plurality of products. The products are then delivered to a summation module 220 of the code removal module 200. A plurality of accumulators 231˜236 of the summation module 220 repeatedly accumulate the corresponding products for a predetermined sampling period to obtain a plurality of series of samples IE, IP, IL, QE, QP, and QL. A dump counter 240 triggers the accumulators 231˜236 to dump the accumulation values therefrom.
FIG. 3 is a schematic diagram of a signal processing course of post-correlation FFT estimation. As previously mentioned, before a FFT is performed on a received signal to obtain FFT values for estimation, a signal carrier carrying data of the signal and a PRN code mixed with the data must be removed from the signal. Thus, a signal S0 is first delivered to a carrier removal module 302 for removal of the signal carrier therefrom. An oscillator 332 generates a carrier signal A with an estimated carrier frequency fcarrier. A phase rotator 313 rotates the phase of the carrier signal A by 90° to obtain a carrier signal A′. Two multipliers 312 and 322 then respectively multiply the signal S0 by the carrier signals A and A′ to obtain signals S1I and S1Q. Two low pass filters 314 and 324 then respectively remove high-frequency signal components from the signals Su and S1Q to obtain signals S21 and S2Q without signal carriers.
The signals S2I and S2Q are then delivered to a code removal module 304 removing a PRN code from the signals. The code removal module 304 has a similar structure to the code removal module 200 of FIG. 2. A code generator 334 generates a PRN code B, and two multipliers 316 and 326 of a correlation module multiply the signals S2I and S2Q by the PRN code B to obtain signals S3I and S3Q without PRN codes. Two integration and dump modules 318 and 328 then repeatedly integrate the signals S3I and S3Q for a duration T and dump the integration values YI and YQ to buffers 319 and 329. The buffers 319 and 329 temporarily hold the integration values YI and YQ.
The integration values YI and YQ are used as input samples of a FFT module 308. Each corresponding pair of the integration values YI and YQ forms a FFT input sample Y with a real part YI and an imaginary part YQ. Because the integration period is T, the sampling frequency of the FFT input samples Y is 1/T. An FFT point number of the FFT module 308 is assumed to be M. Thus, after the FFT module 308 performs a FFT on samples Y0˜YM-1 of time domain, a plurality of FFT values Z0˜ZM-1 of frequency domain are obtained. A signal processor can then estimate a residual Doppler frequency according to the FFT values Z0˜ZM-1.
Because the locally estimated carrier frequency fcarrier is not identical to a true carrier frequency of a satellite transmitting the signal, the residual Doppler frequency, which is the difference between the locally estimated carrier frequency fcarrier and the true carrier frequency, causes signal distortion and affects data extraction and processing, referred to as a residual Doppler effect. The residual Doppler effect can be eliminated by estimating the residual Doppler frequency and adjusting the estimated carrier frequency according to the estimated residual Doppler frequency. Because the signal carrier and the PRN code have been removed from the signals S3I and S3Q, the residual Doppler frequency takes effect in the form of a continuous sinusoidal wave mixed in the signals S3I and S3Q with a frequency of the residual Doppler frequency. Because only a finite segment of the signal S3 is sampled as the input samples of the FFT module 308, the continuous sinusoidal wave with the residual Doppler frequency is converted into a sinc function shown in a signal spectrum diagram of the FFT values Z derived from the signal S3, wherein the center frequency of the sinc function is the residual Doppler frequency. Thus, the residual Doppler frequency can be estimated according to the FFT values Z.
FIG. 4A is a signal spectrum diagram of FFT values for residual Doppler frequency estimation. A dotted line shows signal degradation of residual Doppler effect. A solid line shows signal spectrum of the continuous sinusoidal wave with a frequency of a residual Doppler frequency, which is assumed to be 250 Hz in FIG. 4A. A time domain signal is converted into FFT input samples with a sampling frequency of 1000 Hz. A FFT module then performs FFT on the samples with a FFT point number of 20 to generate FFT values. Thus, the spectrum range of the FFT values is 1000 Hz, ranging from −500 Hz to 500 Hz. 20 FFT values obtained in one FFT conversion are shown in FIG. 4A according to the corresponding frequencies thereof in the form of circles. Among the 20 FFT values, an FFT value 402 corresponding to the frequency of 250 Hz coincides with the center frequency of the main lobe of the residual Doppler wave. Thus, in the case of FIG. 4A, the residual Doppler frequency can be easily estimated by simply locating a corresponding frequency of the FFT value 402 with a maximum magnitude among the FFT values.
FIG. 4B is a signal spectrum diagram of FFT values corresponding to a scalloping loss situation. A residual Doppler frequency does not always coincide with the frequency of one of the FFT values. If the frequencies of FFT values do not exactly match a residual Doppler frequency, the frequency corresponding to the FFT value with the maximum magnitude does not precisely predict the residual Doppler frequency, and scalloping loss occurs. For example, the residual Doppler frequency of FIG. 4B can be 225 Hz, which lies exactly halfway between the frequencies of the FFT values 412 and 414. The frequencies 200 Hz and 250 Hz respectively correspond to the FFT values 412 and 414 with the maximum magnitude, and therefore are not the exact residual Doppler frequency, differing by a frequency bias of 25 Hz therebetween. Thus, a method is provided to estimate a frequency bias between a frequency of the FFT values and a residual Doppler frequency.
FIG. 5 is a signal spectrum diagram of FFT values for estimating a frequency bias from scalloping loss. The residual Doppler frequency of FIG. 5 is 12.5 Hz. Three adjacent FFT values 502, 504, and 506 with maximum magnitudes are first selected from the 20 FFT values. Thus, the three adjacent FFT values 502, 504, and 506 form a magnitude peak roughly overlapping the signal spectrum of the main frequency slope of the residual Doppler wave, and the residual Doppler frequency can be estimated according to the three FFT values. The estimated residual Doppler frequency can be expressed as the frequency 0 Hz of the peak FFT value 504 with the maximum signal magnitude plus a frequency bias of 12.5 Hz. Because the frequency bias is substantially in proportion to the magnitude difference between the left FFT value 502 and the right FFT value 506, the frequency bias 12.5 Hz can be estimated according to the difference between the magnitudes 0.18 and 0.3 of the left FFT value 502 and the right FFT value 506. The estimated residual Doppler frequency is then obtained by adding the frequency of the peak FFT value 504 and the estimated frequency bias.
Precision of estimation of the residual Doppler frequency affects the accuracy of data extraction, further affecting subsequent data processing of the GPS receiver. Because frequency resolution of the FFT module is a factor in determining the estimation precision of the residual Doppler frequency, a higher frequency resolution is desirable. Although the FFT frequency resolution can be increased by increasing FFT point numbers of the FFT module, the increase of FFT point numbers extends a filling time of the FFT module, which indicates a period length of a segment of GPS signal required by the FFT module to generate a set of FFT values. In other words, there is a tradeoff between the frequency resolution and the filling time. The increase in filling time causes the liability of increased signal delay. Thus, a method for improving a frequency resolution of a FFT without increasing filling time is desirable for the estimation of a residual Doppler frequency.